import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;

    public TreeNode createTree(){
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        return a;
    }

    public void preOrder(TreeNode root){
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        ret.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        ret.addAll(left);
        List<Integer> right = preorderTraversal(root.right);
        ret.addAll(right);
        return ret;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        List<Integer> left = inorderTraversal(root.left);
        ret.addAll(left);
        ret.add(root.val);
        List<Integer> right = inorderTraversal(root.right);
        ret.addAll(right);
        return ret;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        List<Integer> left = postorderTraversal(root.left);
        ret.addAll(left);
        List<Integer> right = postorderTraversal(root.right);
        ret.addAll(right);
        ret.add(root.val);
        return ret;
    }

    public int size(TreeNode root){
        if(root == null) return 0;
        return size(root.left) +
                size(root.right) + 1;
    }

    public int getLeafNodeCount(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    public int getKLevelNodeCount(TreeNode root, int k){
        if(root == null) return 0;
        if(k == 1) return 1;
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    public int getHeight(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    public void levelOrder(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            System.out.print(t.val + " ");
            if(t.left != null) queue.offer(t.left);
            if(t.right != null) queue.offer(t.right);
        }
        System.out.println();
    }

    public List<List<TreeNode>> levelOrder2(TreeNode root){
        List<List<TreeNode>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            List<TreeNode> tmp = new ArrayList<>();
            while(sz-- > 0){
                TreeNode t = queue.poll();
                tmp.add(t);
                if(t.left != null) queue.offer(t.left);
                if(t.right != null) queue.offer(t.right);
            }
            ret.add(tmp);
        }
        return ret;
    }

    public boolean isCompleteTree(TreeNode node){
        if(node == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t != null){
                queue.offer(t.left);
                queue.offer(t.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t != null) {
                return false;
            }
        }
        return true;
    }

    public TreeNode find(TreeNode root, int val){
        if(root == null) return null;
        if(root.val == val) return root;
        TreeNode left = find(root.left, val);
        if(left != null) return left;
        else return find(root.right, val);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if((p == null && q != null) || (p != null && q == null)) return false;
        if(p.val != q.val) return false;
        boolean left = isSameTree(p.left, q.left);
        if(!left) return false;
        boolean right = isSameTree(p.right, q.right);
        if(!right) return false;
        return true;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) return false;
        boolean flag = isSameTree(root, subRoot);
        if(flag) return true;
        boolean left = isSubtree(root.left, subRoot);
        if(left) return true;
        boolean right = isSubtree(root.right, subRoot);
        if(right) return true;
        return false;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if(Math.abs(left - right) > 1) return false;
        if(!isBalanced(root.left)) return false;
        if(!isBalanced(root.right)) return false;
        return true;
    }

    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true;
        return dfs(root) > 0;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int left = dfs(root.left);
        if(left == -1) return -1;
        int right = dfs(root.right);
        if(right == -1) return -1;
        if(Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }

    public boolean isSymmetric(TreeNode root) {
        if(isSymmetricTree(root.left, root.right)){
            return true;
        }
        return false;
    }
    public boolean isSymmetricTree(TreeNode t1, TreeNode t2){
        if(t1 == null && t2 == null) return true;
        if((t1 == null && t2 != null) || (t1 != null && t2 == null)) return false;
        if(t1.val != t2.val) return false;
        if(!isSymmetricTree(t1.left, t2.right)) return false;
        if(!isSymmetricTree(t1.right, t2.left)) return false;
        return true;
    }

    // 按照前序遍历的顺序创建二叉树
    public int i;
    public TreeNode createTree(char[] s){
        TreeNode root = null;
        if(s[i] != '#'){
            root = new TreeNode(s[i]);
            i++;
            root.left = createTree();
            root.right = createTree();
        }else{
            i++;
        }
        return root;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null) return root;
        else if(left == null) return right;
        else return left;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP > sizeQ){
            while(sizeP != sizeQ){
                stackP.pop();
                sizeP--;
            }
        }else{
            while(sizeP != sizeQ){
                stackQ.pop();
                sizeQ--;
            }
        }

        while(stackP.peek() != stackQ.peek()){
            stackP.pop();
            stackQ.pop();
        }
        return stackP.peek();
    }
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null) return false;
        stack.push(root);
        if(root == node) return true;
        boolean left = getPath(root.left, node, stack);
        if(left) return true;
        boolean right = getPath(root.right, node, stack);
        if(right) return true;
        stack.pop();
        return false;
    }

    private int preIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        preIndex = 0;

        return createTreeByPreorderAndInorder(preorder, inorder, 0, n - 1);
    }
    private TreeNode createTreeByPreorderAndInorder(int[] preorder, int[] inorder, int begin, int end){
        if(begin > end) return null;

        TreeNode root = new TreeNode(preorder[preIndex]);

        int inorderIndex = getInorderIndex(preorder, inorder, begin, end);

        if(inorderIndex == -1) return null;

        preIndex++;

        root.left = createTreeByPreorderAndInorder(preorder, inorder, begin, inorderIndex - 1);

        root.right = createTreeByPreorderAndInorder(preorder, inorder, inorderIndex + 1, end);

        return root;
    }
    private int getInorderIndex(int[] preorder, int[] inorder, int begin, int end){
        for(int i = begin; i <= end; i++){
            if(preorder[preIndex] == inorder[i]){
                return i;
            }
        }
        return -1;
    }

    public int postIndex;

    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        int n = inorder.length;
        postIndex = n - 1;

        return buildTreeByPostorderAndInorder(postorder, inorder, 0, n - 1);
    }

    public TreeNode buildTreeByPostorderAndInorder(int[] postorder, int[] inorder, int begin, int end){
        if(begin > end) return null;

        TreeNode root = new TreeNode(postorder[postIndex]);

        int inorderIndex = findInorderIndex(postorder, inorder, begin, end);
        if(inorderIndex == -1) return null;

        postIndex--;

        root.right = buildTreeByPostorderAndInorder(postorder, inorder, inorderIndex + 1, end);

        root.left = buildTreeByPostorderAndInorder(postorder, inorder, begin, inorderIndex - 1);

        return root;
    }

    public int findInorderIndex(int[] postorder, int[] inorder, int begin, int end){
        for(int i = begin; i <= end; i++){
            if(inorder[i] == postorder[postIndex]){
                return i;
            }
        }
        return -1;
    }
}
